|
Merge Sort is a comparison-based sorting algorithm by using Divide-and-Conquer. The key idea of Merge Sort is that, a shorter list takes fewer steps than a longer list, and also constructing a sorted list from two sorted lists takes lower time complexity than from two unsorted lists.
Algorithm
- If the list is of length 0 or 1, then it is already sorted. Otherwise:
- Divide the list into two sub-lists of about half of the size
- Sort each sub-list recursively
- Merge the two sub-lists into one sorted list
|
Time Complexity & Space Complexity
Consider the recurrence T(n) = 2T(n/2) + O(n) when assuming merging takes O(n), by the master theorem it will be seen that the time complexity is O(n log n)
Pseudo Code
Function MergeSort( Array[1..n] )
If n <= 1
Report Array[1..n]
var leftSubArray = MergeSort( Array[1..n/2] )
var rightSubArray = MergeSort( Array[n/2+1..n] )
Report Merge( leftSubArray, rightSubArray )
Function Merge( left[1..m], right[1..n] )
var resultArray
while length(left) > 0 or length(right) > 0 then
If length(left) > 0 and length(right) > 0 then
If left[1] <= right[1] then
append left[1] to resultArray
left = left[2..m]
Else
append right[1] to resultArray
right = right[2..n]
Else if length(left) > 0 then
append left[1] to resultArray
left = left[2..m]
Else if length(right) > 0 then
append right[1] to resultArray
right = right[2..n]
end while
Report resultArray
|
|